#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef int ElemType;
typedef struct {
    ElemType *elem;
    ElemType lenth;
} SSTable;

void ST_InIt(SSTable &ST, ElemType lenth) {
    ST.lenth = lenth;
    ST.elem = (ElemType *) malloc(sizeof(ElemType) * ST.lenth);
    srand(time(NULL));
    for (int i = 0; i < ST.lenth; ++i) {
        ST.elem[i] = rand() % 100;
    }
}

void ST_print(SSTable ST) {
    for (int i = 0; i < ST.lenth; ++i) {
        printf("%2d ", ST.elem[i]);
    }
    printf("\n");
}

int BinarySearch(SSTable st, ElemType key) {
    int low = 0, high = st.lenth - 1, mid;
    while (low <= high) {
        mid = (high + low) / 2;
        if (key > st.elem[mid]) {//如果目标值小于中位数
            //将中位数后一个元素下标赋给low
            low = mid + 1;
        } else if (key < st.elem[mid]) {//如果目标值大于中位数
            //将中位数前一个元素下标赋给high
            high = mid - 1;
        } else {//如果目标值等于中位数
            return mid;
        }
    }
    return 0;
}

//函数命存储的是函数的入口地址，也是一个指针，是函数指针类型
//qsort规定如果left指针指向的值大于right指针所指向的值，返回正值，小于则返回负值，相等返回0
//left指针和right指针是指数组中的任意两个元素值
int compare(const void *left, const void *right) {
    return *(int *) left - *(int *) right;
    //return *(int *) right - *(int *) left;
}

//折半查找(二分查找)仅适用于有序的顺序表
//必须是有序的顺序表
int main() {

    /*1.初始化顺序表
     * 2.使用qsort函数进行排序
     * 3.输入要查找的key值，存入变量key中
     * */
    SSTable ST;
    ST_InIt(ST, 10);
    ST_print(ST);
    ElemType key;
    qsort(ST.elem, ST.lenth, sizeof(ElemType), compare);
    ST_print(ST);
    printf("Please enter the value you want to search:");
    scanf("%d", &key);

    int pos = BinarySearch(ST, key);
    if (pos) {
        printf("Search successfully the position is %2d", pos);
    } else {
        printf("Search failed");
    }
    return 0;
}
